Preface to the Digital Edition
The C Programming Language
THE
c
PROGRAMMING
LANGUAGE
Brian W. Kernighan • Dennis M. Ritchie
Contents
Preface to the Digital Edition i
Preface vii
Preface to the First Edition ix
Introduction 1
Chapter 1. A Tutorial Introduction 5
Chapter 2. Types, Operators, and Expressions 35
iv
Chapter 3. Control Flow 55
Chapter 4. Functions and Program Structure 67
Chapter 5. Pointers and Arrays 93
Chapter 6. Structures 127
v
Chapter 7. Input and Output 151
Chapter 8. The UNIX System Interface 169
Preface
The C Programming Language
The C Programming Language
viii
Preface to the First Edition
x
Introduction
if-else
switch
while, for do break
2
The C Programming Language
3
n=n+1
4
if-else switch while for
CHAPTER 1: A Tutorial Introduction
1.1 Getting Started
Print the words
hello,world
6
hello, world
#include <stdio.h>
main()
{
printf("hello, world\n");
}
.c hello.c
cc hello.c
a.out a.out
a.out
hello, world
functions variables statements
main
main
main main
main
#include <stdio.h>
arguments
7
#include <stdio.h> include information about standard library
main() dene a function named main
that receives no argument values
{ statements of main are enclosed in braces
printf("hello, world\n"); main calls library function printf
to print this sequence of characters;
\n represents the newline character
}
The first C program
main
()
{} main
printf("hello, world\n");
printf "hello, world\n"
printf
"hello, world\n"
character string string constant.
printf
\n newline character
\n
\n
printf
printf("hello, world
");
printf
8
#include <stdio.h>
main()
{
printf("hello, ");
printf("world");
printf("\n");
}
\n escape sequence
\n
\t \b
\" \\
Exercise 1-1 hello, world
□
Exercise 1-2 printf
\c c □
1.2 Variables and Arithmetic Expressions
C F
0 -17
20 -6
40 4
60 15
80 26
100 37
120 48
140 60
160 71
180 82
200 93
220 104
240 115
260 126
280 137
300 148
main hello, world
9
#include <stdio.h>
/* print Fahrenheit-Celsius table
for fahr = 0, 20, ..., 300 */
main()
{
int fahr, celsius;
int lower, upper, step;
lower = 0; /* lower limit of temperature table */
upper = 300; /* upper limit */
step = 20; /* step size */
fahr = lower;
while (fahr <= upper) {
celsius = 5 * (fahr-32) / 9;
printf("%d\t%d\n", fahr, celsius);
fahr = fahr + step;
}
}
/* print Fahrenheit-Celsius table
for fahr = 0, 20, ..., 300 */
comment
/* */
declaration
int fahr, celsius;
int lower, upper, step;
int float
int float
int int
float
−
+
int float
char
short
long
double
10
arrays
structures unions functions
as-
signment statements
lower = 0;
upper = 300;
step = 20;
fahr = lower;
while
while (fahr <= upper) {
}
while
fahr upper
fahr
upper
while
while (i < j)
i = 2 * i;
while
celsius
celsius = 5 * (fahr-32) / 9;
5/9 truncates
5 9 5/9
11
printf printf
%
%d
printf("%d\t%d\n", fahr, celsius);
fahr celsius
\t
% printf
printf
printf
printf
scanf
scanf printf
%d printf
printf("%3d %6d\n", fahr, celsius);
0 -17
20 -6
40 4
60 15
80 26
100 37
12
#include <stdio.h>
/* print Fahrenheit-Celsius table
for fahr = 0, 20, ..., 300; floating-point version */
main()
{
float fahr, celsius;
int lower, upper, step;
lower = 0; /* lower limit of temperature table */
upper = 300; /* upper limit */
step = 20; /* step size */
fahr = lower;
while (fahr <= upper) {
celsius = (5.0/9.0) * (fahr-32.0);
printf("%3.0f %6.1f\n", fahr, celsius);
fahr = fahr + step;
}
}
fahr celsius
float
5/9
5.0/9.0
fahr − 32 32
fahr = lower;
while (fahr <= upper)
int float
printf %3.0f
fahr
%6.1f celsius
13
0 -17.8
20 -6.7
40 4.4
%6f
%.2f
%f
%d
%6d
%f
%6f
%.2f
%6.2f
printf %o %x %c
%s %% %
Exercise 1-3
□
Exercise 1-4
□
1.3 The For Statement
#include <stdio.h>
/* print Fahrenheit-Celsius table */
main()
{
int fahr;
for (fahr = 0; fahr <= 300; fahr = fahr + 20)
printf("%3d %6.1f\n", fahr, (5.0/9.0)*(fahr-32));
}
fahr
int
for
printf
14
printf
%6.1f
for while
while
fahr = 0
fahr <= 300
printf
fahr = fahr + 20
while
while for
for
while
Exercise 1-5
□
1.4 Symbolic Constants
#define symbolic
name symbolic constant
#define name replacement text
name
replacement text name
replacement text
15
#include <stdio.h>
#define LOWER 0 /* lower limit of table */
#define UPPER 300 /* upper limit */
#define STEP 20 /* step size */
/* print Fahrenheit-Celsius table */
main()
{
int fahr;
for (fahr = LOWER; fahr <= UPPER; fahr = fahr + STEP)
printf("%3d %6.1f\n", fahr, (5.0/9.0)*(fahr-32));
}
LOWER UPPER STEP
#define
1.5 Character Input and Output
text stream
getchar putchar
getchar next input character
c = getchar();
c
putchar
putchar(c);
c
putchar printf
16
1.5.1 File Copying
getchar putchar
read a character
while (character is not end-of-le indicator)
output the character just read
read a character
#include <stdio.h>
/* copy input to output; 1st version */
main()
{
int c;
c = getchar();
while (c != EOF) {
putchar(c);
c = getchar();
}
}
!=
char
int
getchar
EOF
c
getchar char c
EOF char int
EOF <stdio.h>
char
c = getchar();
17
c
while
#include <stdio.h>
/* copy input to output; 2nd version */
main()
{
int c;
while ((c = getchar()) != EOF)
putchar(c);
}
while c
while
while
while main
getchar
precedence != =
!= =
c = getchar() != EOF
c = (getchar() != EOF)
c
getchar
Exercise 1-6 getchar() != EOF □
Exercise 1-7 EOF □
1.5.2 Character Counting
#include <stdio.h>
18
/* count characters in input; 1st version */
main()
{
long nc;
nc = 0;
while (getchar() != EOF)
++nc;
printf("%ld\n", nc);
}
++nc;
++ increment by one.
nc = nc + 1 ++nc
-- ++ --
++nc nc++
++nc nc++
nc
long
int long
int long int
int
%ld printf
long
double
float for while
#include <stdio.h>
/* count characters in input; 2nd version */
main()
{
double nc;
for (nc = 0; getchar() != EOF; ++nc)
;
printf("%.0f\n", nc);
}
printf %f float double; %.0f
for
for
null statement
while for
19
getchar
while for
while for
1.5.3 Line Counting
#include <stdio.h>
/* count lines in input */
main()
{
int c, nl;
nl = 0;
while ((c = getchar()) != EOF)
if (c == '\n')
++nl;
printf("%d\n", nl);
}
while if
++nl if
==
= .EQ.
=
= ==
character constant
'A'
A 'A'
65
'\n'
'\n'
"\n"
20
Exercise 1-8 □
Exercise 1-9
□
Exercise 1-10
\t \b \\
□
1.5.4 Word Counting
wc
#include <stdio.h>
#define IN 1 /* inside a word */
#define OUT 0 /* outside a word */
/* count lines, words, and characters in input */
main()
{
int c, nl, nw, nc, state;
state = OUT;
nl = nw = nc = 0;
while ((c = getchar()) != EOF) {
++nc;
if (c == '\n')
++nl;
if (c == ' ' || c == '\n' || c == '\t')
state = OUT;
else if (state == OUT) {
state = IN;
++nw;
}
}
printf("%d %d %d\n", nl, nw, nc);
}
state
OUT
IN OUT
21
nl = nw = nc = 0
nl = (nw = (nc = 0));
||
if (c == ' ' || c == '\n' || c = '\t')
c or c or c
\t
&& ||
&& ||
c
else
if
if (expression)
statement
1
else
statement
2
if-else
expression statement
1
statement
2
statement
else if
Exercise 1-11
□
Exercise 1-12 □
1.6 Arrays
22
#include <stdio.h>
/* count digits, white space, others */
main()
{
int c, i, nwhite, nother;
int ndigit[10];
nwhite = nother = 0;
for (i = 0; i < 10; ++i)
ndigit[i] = 0;
while ((c = getchar()) != EOF)
if (c >= '0' && c <= '9')
++ndigit[c-'0'];
else if (c == ' ' || c == '\n' || c == '\t')
++nwhite;
else
++nother;
printf("digits =");
for (i = 0; i < 10; ++i)
printf(" %d", ndigit[i]);
printf(", white space = %d, other = %d\n",
nwhite, nother);
}
digits = 9 3 0 0 0 0 0 0 0 1, white space = 123, other = 345
int ndigit[10];
ndigit
ndigit[0] ndigit[1] ndigit[9]
for
i
if (c >= '0' && c <= '9')
c
c - '0'
23
'0' '1' '9'
char char
int
c-'0'
'0' '9' c
ndigit
if (c >= '0' && c <= '9')
++ndigit[c-'0'];
else if (c == ' ' || c == '\n' || c == '\t')
++nwhite;
else
++nother;
if (condition
1
)
statement
1
else if (condition
2
)
statement
2
...
...
else
statement
n
condition condition
statement
statement
statement else
else statement
else if (condition)
statement
if else
if else
24
switch
switch
Exercise 1-13
□
Exercise 1-14
□
1.7 Functions
how what
printf getchar putchar
**
power(m,n) m
n power(2,5)
pow(x,y) x
y
power
#include <stdio.h>
int power(int m, int n);
/* test power function */
main()
{
int i;
for (i = 0; i < 10; ++i)
printf("%d %d %d\n", i, power(2,i), power(-3,i));
return 0;
}
25
/* power: raise base to n-th power; n >= 0 */
int power(int base, int n)
{
int i, p;
p = 1;
for (i = 1; i <= n; ++i)
p = p * base;
return p;
}
return-type function-nameparameter declarations, if any
{
declarations
statements
}
power main
printf("%d %d %d\n", i, power(2,i), power(-3,i));
power
power(2,i)
2 i
power
int power(int base, int n)
power power
i p i power
i main
parameter
argument
formal argument actual argument
power main return
return
return expression;
26
return
return main
main
return main
int power(int base, int n);
main power int
int function prototype
power
int power(int, int);
power
/* power: raise base to n-th power; n >= 0 */
/*
(old-style version) */
power(base, n)
int base, n;
{
int i, p;
p = 1;
for (i = 1; i <= n; ++i)
p = p * base;
return p;
}
int
power
27
int power();
power power
int
Exercise 1-15
□
1.8 Arguments — Call by Value
var
power
/* power: raise base to n-th power; n>=0; version 2 */
int power(int base, int n)
{
int p;
for (p = 1; n > 0; --n)
p = p * base;
return p;
}
n for
i n power
power
28
address
pointer
1.9 Character Arrays
while (there’s another line)
if (it’s longer than the previous longest)
save it
save its length
print longest line
getline
getline
copy
getline copy
29
#include <stdio.h>
#define MAXLINE 1000 /* maximum input line size */
int getline(char line[], int maxline);
void copy(char to[], char from[]);
/* print longest input line */
main()
{
int len; /* current line length */
int max; /* maximum length seen so far */
char line[MAXLINE]; /* current input line */
char longest[MAXLINE]; /* longest line saved here */
max = 0;
while ((len = getline(line, MAXLINE)) > 0)
if (len > max) {
max = len;
copy(longest, line);
}
if (max > 0) /* there was a line */
printf("%s", longest);
return 0;
}
/* getline: read a line into s, return length */
int getline(char s[], int lim)
{
int c, i;
for (i=0; i<lim-1 && (c=getchar())!=EOF && c!='\n'; ++i)
s[i] = c;
if (c == '\n') {
s[i] = c;
++i;
}
s[i] = '\0';
return i;
}
/* copy: copy 'from' into 'to'; assume to is big enough */
void copy(char to[], char from[])
{
int i;
i = 0;
while ((to[i] = from[i]) != '\0')
++i;
}
30
getline copy
main getline
getline
int getline(char s[], int lim);
s lim
s getline
main getline return
power getline int
int
copy
copy void
getline '\0' null character
"hello\n"
'\0'
h e l l o \n \0
%s printf
copy
'\0'
'\0'
main
getline
main
getline
getline
copy
Exercise 1-16
□
31
Exercise 1-17
□
Exercise 1-18
□
Exercise 1-19 reverse(s)
s □
1.10 External Variables and Scope
main line longest
main main
i getline i copy
automatic
static
external
dened
declared
extern
line longest
max
32
#include <stdio.h>
#define MAXLINE 1000 /* maximum input line size */
int max; /* maximum length seen so far */
char line[MAXLINE]; /* current input line */
char longest[MAXLINE]; /* longest line saved here */
int getline(void);
void copy(void);
/* print longest input line; specialized version */
main()
{
int len;
extern int max;
extern char longest[];
max = 0;
while ((len = getline()) > 0)
if (len > max) {
max = len;
copy();
}
if (max > 0) /* there was a line */
printf("%s", longest);
return 0;
}
/* getline: specialized version */
int getline(void)
{
int c, i;
extern char line[];
for (i = 0; i < MAXLINE-1
&& (c=getchar()) != EOF && c != '\n'; ++i)
line[i] = c;
if (c == '\n') {
line[i] = c;
++i;
}
line[i] = '\0';
return i;
}
33
/* copy: specialized version */
void copy(void)
{
int i;
extern char line[], longest[];
i = 0;
while ((longest[i] = line[i]) != '\0')
++i;
}
main getline copy
extern
extern
extern
extern
extern main getline copy
extern
le1
le2 le3 extern le2 le3
extern
header #include
.h
<stdio.h>
getline copy
getline() copy()
void
denition declaration
extern
34
Exercise 1-20 detab
n n
□
Exercise 1-21 entab
detab
□
Exercise 1-22
n
□
Exercise 1-23
□
Exercise 1-24
□
CHAPTER 2: Types, Operators, and Expressions
signed unsigned
long double
const
2.1 Variable Names
"_"
x X
36
if else int float
2.2 Data Types and Sizes
char
int
float
double
short long
short int sh;
long int counter;
int
short long
int
short long int
short int long
short int long
signed unsigned char
unsigned
n
char unsigned char
signed char
char
long double
float
double long double
<limits.h> <float.h>
37
Exercise 2-1 char short int
long signed unsigned
□
2.3 Constants
1234 int long
l L 123456789L int
long u U
ul UL unsigned long
123.4
1e−2 double f F
float l L long double
0 0x
0X 037
0x1f 0X1F
L long U unsigned 0XFUL
unsigned long
character constant
'x'
'0'
0 '0'
\n
'\ooo'
ooo
'\xhh'
hh 09 af AF
#define VTAB '\013' /* ASCII vertical tab */
#define BELL '\007' /* ASCII bell character */
38
#define VTAB '\xb' /* ASCII vertical tab */
#define BELL '\x7' /* ASCII bell character */
\a
\b
\f
\n
\r
\t
\v
\\
\?
\'
\"
\ooo
\xhh
'\0'
'\0' 0
constant expression
#define MAXLINE 1000
char line[MAXLINE+1];
#define LEAP 1 /* in leap years */
int days[31+28+LEAP+31+30+31+30+31+31+30+31+30+31];
string constant string literal
"I am a string"
"" /* the empty string */
\"
"hello," " world"
"hello, world"
'\0'
strlen(s)
s '\0'
39
/* strlen: return length of s */
int strlen(char s[])
{
int i;
i = 0;
while (s[i] != '\0')
++i;
return i;
}
strlen
<string.h>
'x' "x"
x
x
'\0'
enumeration constant
enum boolean{ NO, YES };
enum
enum escapes { BELL = '\a', BACKSPACE = '\b', TAB = '\t',
NEWLINE = '\n', VTAB = '\v', RETURN = '\r' };
enum months { JAN = 1, FEB, MAR, APR, MAY, JUN,
JUL, AUG, SEP, OCT, NOV, DEC };
/* FEB is 2, MAR is 3, etc. */
#define
enum
#define
40
2.4 Declarations
int lower, upper, step;
char c, line[1000];
int lower;
int upper;
int step;
char c;
char line[1000];
char esc = '\\';
int i = 0;
int limit = MAXLINE+1;
float eps = 1.0e-5;
const
const
const double e = 2.71828182845905;
const char msg[] = "warning: ";
const
int strlen(const char[]);
const
41
2.5 Arithmetic Operators
+ - / %
x % y
x y y
x
are
if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
printf("%d is a leap year\n", year);
else
printf("%d is not a leap year\n", year);
% float double
/ %
+ -
*
, / % + -
2.6 Relational and Logical Operators
> >= < <=
== !=
i < lim−1 i < (lim−1)
&& ||
&& ||
getline
for (i=0; i<lim −1 && (c=getchar()) != '\n' && c != EOF; ++i)
s[i] = c;
s i < lim−1 must
42
c EOF
getchar
c
&& ||
i < lim − 1 && (c = getchar()) != '\n' && c != EOF
!=
(c = getchar()) != '\n'
c '\n'
!
!
if (!valid)
if (valid == 0)
!valid
Exercise 2-2 for &&
|| □
2.7 Type Conversions
f + i
float
char char
atoi
43
/* atoi: convert s to integer */
int atoi(char s[])
{
int i, n;
n = 0;
for (i = 0; s[i] >= '0' && s[i] <= '9'; ++i)
n = 10 * n + (s[i] - '0');
return n;
}
s[i] - '0'
s[i]
'0' '1'
char int lower
for the ASCII character set
lower
/* lower: convert c to lower case; ASCII only */
int lower(int c)
{
if (c >= 'A' && c <= 'Z')
return c + 'a' - 'A';
else
return c;
}
A Z
<ctype.h>
tolower(c) c
c tolower lower
c >= '0' && c <= '9'
isdigit(c)
<ctype.h>
char
char int
char
44
char
int
signed unsigned
char
i > j &&
||
d = c >= '0' && c <= '9'
d c isdigit
if while for
+
*
promoted
unsigned
long double long double
double double
float float
char short int
long long
float
double
<math.h>
float
unsigned
int long −1L
< 1U 1U int signed long −1L >
1UL −1L unsigned long
45
char
int i;
char c;
i = c;
c = i;
c
x float i int x = i i = x
float int double
float
char short int float double
int double
char float
cast.
(type-name) expression
expression
expression
sqrt double
sqrt
<math.h> n
sqrt((double) n)
n double sqrt
value n n
sqrt
double sqrt(double);
root2 = sqrt(2);
2 double 2.0
46
unsigned long int next = 1;
/* rand: return pseudo-random integer on 0..32767 */
int rand(void)
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
/* srand: set seed for rand() */
void srand(unsigned int seed)
{
next = seed;
}
Exercise 2-3 htoi(s)
0x 0X
0 9 a f A F □
2.8 Increment and Decrement Operators
++
-- ++
if (c == '\n')
++nl;
++ --
++n n++
n ++n n before
n++ n after
++n n++
n
x = n++;
x
x = ++n;
x n
(i+j)++
47
if (c == '\n')
nl++;
squeeze(s,c)
c s
/* squeeze: delete all c from s */
void squeeze(char s[], int c)
{
int i, j;
for (i = j = 0; s[i] != '\0'; i++)
if (s[i] != c)
s[j++] = s[i];
s[j] = '\0';
}
c j
j
if (s[i] != c) {
s[j] = s[i];
j++;
}
getline
if (c == '\n') {
s[i] = c;
++i;
}
if (c == '\n')
s[i++] = c;
strcat(s,t)
t s strcat
s strcat
48
/* strcat: concatenate t to end of s; s must be big enough */
void strcat(char s[], char t[])
{
int i, j;
i = j = 0;
while (s[i] != '\0') /* find end of s */
i++;
while ((s[i++] = t[j++]) != '\0') /* copy t */
;
}
t s ++ i
j
Exercise 2-4 squeeze(s1,s2)
s1 string s2 □
Exercise 2-5 any(s1,s2)
s1 s2 −1 s1
s2 strpbrk
□
2.9 Bitwise Operators
char short int long
&
|
^
<<
>>
~
&
n = n & 0177;
n
|
x = x | SET_ON;
x SET_ON
^
49
& |
&& ||
x y x & y x && y
<< >>
x << 2 x
unsigned
~
x = x & ~077
x x & ~077
x & 0177700
x ~077
getbits(x,p,n) n x
p n p
getbits(x,4,3)
/* getbits: get n bits from position p */
unsigned getbits(unsigned x, int p, int n)
{
return (x >> (p+1-n)) & ~(~0 << n);
}
x >> (p+1-n)
~0 n ~0<<n
n ~
n
Exercise 2-6 setbits(x,p,n,y) x n
p n y
□
Exercise 2-7 invert(x,p,n) x n
p
□
Exercise 2-8 rightrot(x,n)
x n □
50
2.10 Assignment Operators and Expressions
i = i + 2
i += 2
+= assignment operator.
+
op = op
+ - * / % << >> & ^ |
expr
1
expr
2
expr
1
op = expr
2
expr
1
= (expr
1
) op (expr
2
)
expr
1
expr
2
x *= y + 1
x = x * (y + 1)
x = x * y + 1
bitcount
/* bitcount: count 1 bits in x */
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}
x unsigned
i
51
i i i
i += 2 i = i+2
yyval[yypv[p3+p4] + yypv[p1+p2]] += 2
while ((c = getchar()) != EOF)
+= -=
Exercise 2-9 x &= (x−1)
x
bitcount □
2.11 Conditional Expressions
if (a > b)
z = a;
else
z = b;
z a b conditional expression
"?:"
expr
1
? expr
2
: expr
3
expr
1
expr
2
expr
3
expr
2
expr
3
z a b
z = (a > b) ? a : b; /* z = max(a, b) */
expr
2
expr
3
52
f float n int
(n > 0) ? f : n
float n
?:
n
for (i = 0; i < n; i++)
printf("%6d%c", a[i], (i%10==9 || i==n-1) ? '\n' : ' ');
n
if-else
printf("You have %d item%s.\n", n, n==1 ? "" : "s");
Exercise 2-10 lower
if-else □
2.12 Precedence and Order of Evaluation
*
, / %
+ - () ->
.
sizeof
*
&
& ^ | ==
!=
if ((x & MASK) == 0)
&& || ?: ','
53
() [] -> .
! ~ ++ -- + - * & type sizeof
* / %
+ -
<< >>
< <= > >=
== !=
&
^
|
&&
||
?:
= += -= *= /= %= &= ^= |= <<= >>=
,
+ - *
x = f() + g();
f g f g
x
printf("%d %d\n", ++n, power(2, n)); /* WRONG */
n
power
++n;
printf("%d %d\n", n, power(2, n));
a[i] = i++;
i
54
printf
how
CHAPTER 3: Control Flow
3.1 Statements and Blocks
x = 0 i++ printf() statement
x = 0;
i++;
printf(...);
{ }
compound statement block
if else while
for any
3.2 If-Else
if-else
if (expression)
statement
1
else
statement
2
56
else expression
expression statement
ex-
pression else statement
2
if
if (expression)
if (expression != 0)
else if-else
else if
else else if
if (n > 0)
if (a > b)
z = a;
else
z = b;
else if
if (n > 0) {
if (a > b)
z = a;
}
else
z = b;
if (n >= 0)
for (i = 0; i < n; i++)
if (s[i] > 0) {
printf("...");
return i;
}
else /* WRONG */
printf("error -- n is negative\n");
else if
if
z = a
57
if (a > b)
z = a;
else
z = b;
statement if
"z = a;"
3.3 Else-If
if (expression)
statement
else if (expression)
statement
else if (expression)
statement
else if (expression)
statement
else
statement
if
expres-
sions expression statement
statement
else
else
statement
x v v
0
n−1 x v −1
x
v x
x
58
/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
int binsearch(int x, int v[], int n)
{
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high) {
mid = (low+high) / 2;
if (x < v[mid])
high = mid - 1;
else if (x > v[mid])
low = mid + 1;
else /* found match */
return mid;
}
return -1; /* no match */
}
x
v[mid] else-if
Exercise 3-1
□
3.4 Switch
switch
constant
switch (expression) {
case const-expr : statement
case const-expr : statement
default: statement
}
default
default
if else if
else switch
59
#include <stdio.h>
main() /* count digits, white space, others */
{
int c, i, nwhite, nother, ndigit[10];
nwhite = nother = 0;
for (i = 0; i < 10; i++)
ndigit[i] = 0;
while ((c = getchar()) != EOF) {
switch (c) {
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
ndigit[c-'0']++;
break;
case ' ':
case '\n':
case '\t':
nwhite++;
break;
default:
nother++;
break;
}
}
printf("digits =");
for (i = 0; i < 10; i++)
printf(" %d", ndigit[i]);
printf(", white space = %d, other = %d\n",
nwhite, nother);
return 0;
}
break switch
falls
through break return
switch break
while for do
break
break default
60
Exercise 3-2 escape(s,t)
\n \t t
s switch
□
3.5 Loops—While and For
while for
while (expression)
statement
expression statement expres-
sion expression
statement.
for
for (expr
1
; expr
2
; expr
3
)
statement
expr
1
;
while (expr
2
) {
statement
expr
3
;
}
continue
for
expr
1
expr
3
expr
2
expr
1
expr
3
expr
2
for (;;) {
}
break
return
while for
while ((c = getchar()) == ' ' || c == '\n' || c == '\t')
; /* skip white space characters */
while
61
for
for (i = 0; i < n; i++)
n
for
for
i
for for
for
atoi
+ -
atof
skip white space, if any
get sign, if any
get integer part and convert it
#include <ctype.h>
/* atoi: convert s to integer; version 2 */
int atoi(char s[])
{
int i, n, sign;
for (i = 0; isspace(s[i]); i++) /* skip white space */
;
sign = (s[i] == '-') ? -1 : 1;
if (s[i] == '+' || s[i] == '-') /* skip sign */
i++;
for (n = 0; isdigit(s[i]); i++)
n = 10 * n + (s[i] - '0');
return sign * n;
}
strtol
62
/* shellsort: sort v[0]...v[n-1] into increasing order */
void shellsort(int v[], int n)
{
int gap, i, j, temp;
for (gap = n/2; gap > 0; gap /= 2)
for (i = gap; i < n; i++)
for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) {
temp = v[j];
v[j] = v[j+gap];
v[j+gap] = temp;
}
}
n/2
gap
gap
for
","
for
for
reverse(s) s
#include <string.h>
/* reverse: reverse string s in place */
void reverse(char s[])
{
int c, i, j;
for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
63
not
for reverse
reverse
for (i = 0, j = strlen(s)−1; i < j; i++, j--)
c = s[i]; s[i] = s[j]; s[j] = c;
Exercise 3-3 expand(s1,s2)
a-z s1 abc...xyz
s2
a-b-c a-z0−9 -a-z -
□
3.6 Loops—Do-while
while for
do-while
after
do
do
statement
while (expression);
statement expression statement
do-while
repeat-until
do-while while for
itoa
atoi
64
/* itoa: convert n to characters in s */
void itoa(int n, char s[])
{
int i, sign;
if ((sign = n) < 0) /* record sign */
n = -n; /* make n positive */
i = 0;
do { /* generate digits in reverse order */
s[i++] = n % 10 + '0'; /* get next digit */
} while ((n /= 10) > 0); /* delete it */
if (sign < 0)
s[i++] = '-';
s[i] = '\0';
reverse(s);
}
do-while
s n
do-while
while
beginning while
Exercise 3-4
itoa n
□
Exercise 3-5 itob(n,s,b) n
b s itob(n,s,16)
n s □
Exercise 3-6 itoa
□
3.7 Break and Continue
break for
while do switch break
switch
trim
break
65
/* trim: remove trailing blanks, tabs, newlines */
int trim(char s[])
{
int n;
for (n = strlen(s)-1; n >= 0; n--)
if (s[n] != ' ' && s[n] != '\t' && s[n] != '\n')
break;
s[n+1] = '\0';
return n;
}
strlen for
n
continue break
for while do while
do for
continue
switch continue switch
a
for (i = 0; i < n; i++) {
if (a[i] < 0) /* skip negative elements */
continue;
/* do positive elements */
}
continue
3.8 Goto and Labels
goto
goto
goto
goto
break
66
for ( )
for ( ) {
if (disaster)
goto error;
}
error:
clean up the mess
goto
a b
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if (a[i] == b[j])
goto found;
/* didn't find any common element */
found:
/* got one: a[i] == b[j] */
goto
found = 0;
for (i = 0; i < n && !found; i++)
for (j = 0; j < m && !found; j++)
if (a[i] == b[j])
found = 1;
if (found)
/* got one: a[i-1] == b[j-1] */
else
/* didn't find any common element */
goto
goto goto
CHAPTER 4: Functions and Program Structure
4.1 Basics of Functions
grep
68
"ould"
Ah Love! could you and I with Fate conspire
To grasp this sorry Scheme of Things entire,
Would not we shatter it to bits -- and then
Re-mould it nearer to the Heart's Desire!
Ah Love! could you and I with Fate conspire
Would not we shatter it to bits -- and then
Re-mould it nearer to the Heart's Desire!
while (there’s another line)
if (the line contains the pattern)
print it
main
getline
printf
strindex(s,t)
s t −1
s t
−1
strindex
strstr strindex
getline
69
#include <stdio.h>
#define MAXLINE 1000 /* maximum input line length */
int getline(char line[], int max);
int strindex(char source[], char searchfor[]);
char pattern[] = "ould"; /* pattern to search for */
/* find all lines matching pattern */
main()
{
char line[MAXLINE];
int found = 0;
while (getline(line, MAXLINE) > 0)
if (strindex(line, pattern) >= 0) {
printf("%s", line);
found++;
}
return found;
}
/* getline: get line into s, return length */
int getline(char s[], int lim)
{
int c, i;
i = 0;
while (--lim > 0 && (c=getchar()) != EOF && c != '\n')
s[i++] = c;
if (c == '\n')
s[i++] = c;
s[i] = '\0';
return i;
}
/* strindex: return index of t in s, -1 if none */
int strindex(char s[], char t[])
{
int i, j, k;
for (i = 0; s[i] != '\0'; i++) {
for (j=i, k=0; t[k]!='\0' && s[j]==t[k]; j++, k++)
;
if (k > 0 && t[k] == '\0')
return i;
}
return -1;
}
70
return-type function-name(argument declarations)
{
declarations and statements
}
dummy() {}
int
return
return
return expression
expression
expression
return
main
cc
main.c getline.c
strindex.c
cc main.c getline.c strindex.c
main.o
getline.o strindex.o
a.out main.c
cc main.c getline.o strindex.o
cc ".c" ".o"
71
Exercise 4-1 strrindex(s,t)
rightmost t s −1 □
4.2 Functions Returning Non-integers
void
int
sqrt sin cos double
atof(s) s
atof atoi
not
atof <stdlib.h>
atof int
#include <ctype.h>
/* atof: convert string s to double */
double atof(char s[])
{
double val, power;
int i, sign;
for (i = 0; isspace(s[i]); i++) /* skip white space */
;
sign = (s[i] == '-') ? -1 : 1;
if (s[i] == '+' || s[i] == '-')
i++;
for (val = 0.0; isdigit(s[i]); i++)
val = 10.0 * val + (s[i] - '0');
if (s[i] == '.')
i++;
for (power = 1.0; isdigit(s[i]); i++) {
val = 10.0 * val + (s[i] - '0');
power *= 10.0;
}
return sign * val / power;
}
atof
int atof
72
#include <stdio.h>
#define MAXLINE 100
/* rudimentary calculator */
main()
{
double sum, atof(char []);
char line[MAXLINE];
int getline(char line[], int max);
sum = 0;
while (getline(line, MAXLINE) > 0)
printf("\t%g\n", sum += atof(line));
return 0;
}
double sum, atof(char []);
sum double atof
char[] double
atof atof
main
atof
atof double
main int
sum += atof(line)
int
double atof();
atof;
73
void
atof atoi
int
/* atoi: convert string s to integer using atof */
int atoi(char s[])
{
double atof(char s[]);
return (int) atof(s);
}
return
return expression
atof double int
return atoi int
Exercise 4-2 atof
123.45e-6
e E
□
4.3 External Variables
external linkage
74
+ -
*
/
(1 - 2) * (4 + 5)
1 2 - 4 5 + *
75
while (next operator or operand is not end-of-le indicator)
if (number)
push it
else if (operator)
pop operands
do operation
push result
else if (newline)
pop and print top of stack
else
error
main
main
push
pop main
#includes
#defines
function declarations for main
main() { }
external variables for push and pop
void push(double f) { }
double pop(void) { }
int getop(char s[]) { }
routines called by getop
main switch
switch
76
#include <stdio.h>
#include <stdlib.h> /* for atof() */
#define MAXOP 100 /* max size of operand or operator */
#define NUMBER '0' /* signal that a number was found */
int getop(char []);
void push(double);
double pop(void);
/* reverse Polish calculator */
main()
{
int type;
double op2;
char s[MAXOP];
while ((type = getop(s)) != EOF) {
switch (type) {
case NUMBER:
push(atof(s));
break;
case '+':
push(pop() + pop());
break;
case '*':
push(pop() * pop());
break;
case '-':
op2 = pop();
push(pop() - op2);
break;
case '/':
op2 = pop();
if (op2 != 0.0)
push(pop() / op2);
else
printf("error: zero divisor\n");
break;
case '\n':
printf("\t%.8g\n", pop());
break;
default:
printf("error: unknown command %s\n", s);
break;
}
}
return 0;
}
77
+
*
- /
push(pop() - pop()); /* WRONG */
pop
main
#define MAXVAL 100 /* maximum depth of val stack */
int sp = 0; /* next free stack position */
double val[MAXVAL]; /* value stack */
/* push: push f onto value stack */
void push(double f)
{
if (sp < MAXVAL)
val[sp++] = f;
else
printf("error: stack full, can't push %g\n", f);
}
/* pop: pop and return top value from stack */
double pop(void)
{
if (sp > 0)
return val[--sp];
else {
printf("error: stack empty\n");
return 0.0;
}
}
push pop
main
getop
NUMBER
78
#include <ctype.h>
int getch(void);
void ungetch(int);
/* getop: get next operator or numeric operand */
int getop(char s[])
{
int i, c;
while ((s[0] = c = getch()) == ' ' || c == '\t')
;
s[1] = '\0';
if (!isdigit(c) && c != '.')
return c; /* not a number */
i = 0;
if (isdigit(c)) /* collect integer part */
while (isdigit(s[++i] = c = getch()))
;
if (c == '.') /* collect fraction part */
while (isdigit(s[++i] = c = getch()))
;
s[i] = '\0';
if (c != EOF)
ungetch(c);
return NUMBER;
}
getch ungetch
getch
ungetch
getch
ungetch
getch
getchar
getch ungetch
getch ungetch
79
#define BUFSIZE 100
char buf[BUFSIZE]; /* buffer for ungetch */
int bufp = 0; /* next free position in buf */
int getch(void) /* get a (possibly pushed back) character */
{
return (bufp > 0) ? buf[--bufp] : getchar();
}
void ungetch(int c) /* push character back on input */
{
if (bufp >= BUFSIZE)
printf("ungetch: too many characters\n");
else
buf[bufp++] = c;
}
ungetc
Exercise 4-3
% □
Exercise 4-4
□
Exercise 4-5 sin exp pow
<math.h> □
Exercise 4-6
□
Exercise 4-7 ungets(s)
ungets buf bufp
ungetch □
Exercise 4-8
getch ungetch □
Exercise 4-9 getch ungetch EOF
EOF
□
Exercise 4-10 getline
getch ungetch
□
80
4.4 Scope Rules
scope
main sp
val push pop
main() { }
int sp = 0;
double val[MAXVAL];
void push(double f) { }
double pop(void) { }
sp val push pop
main push pop
extern
declaration
denition.
int sp;
double val[MAXVAL];
81
dene sp val
extern int sp;
extern double val[];
declare sp int val double
denition
extern
extern
extern
push
pop val sp
In le1:
extern int sp;
extern double val[];
void push(double f) { }
double pop(void) { }
In le2:
int sp = 0;
double val[MAXVAL];
extern le1
le1 sp
val
4.5 Header Files
main main.c; push pop
stack.c getop getop.c
getch ungetch getch.c
82
header le calc.h
#include
main.c:
#include <stdio.h>
#include <stdlib.h>
#include "calc.h"
#define MAXOP 100
main() {
...
}
calc.h:
#define NUMBER '0'
void push(double);
double pop(void);
int getop(char []);
int getch(void);
void ungetch(int);
getop.c:
#include <stdio.h>
#include <ctype.h>
#include "calc.h"
getop() {
...
}
getch.c:
#include <stdio.h>
#define BUFFSIZE 100
char buf[BUFSIZE];
int bufp = 0;
int getch(void) {
...
}
int ungetch(int) {
...
}
stack.c:
#include <stdio.h>
#include "calc.h"
#define MAXVAL 100
int sp = 0;
double val[MAXVAL]
int push(double) {
...
}
int pop(void) {
...
}
83
4.6 Static Variables
sp val stack.c buf bufp getch.c
static
static
buf bufp getch-ungetch
getch
ungetch
static
static char buf[BUFSIZE]; /* buffer for ungetch */
static int bufp = 0; /* next free position in buf */
int getch(void) { }
void ungetch(int c) { }
buf bufp
push pop
sp val static
static
static
static
static
static
Exercise 4-11 getop ungetch
static □
4.7 Register Variables
register
register
register
84
register int x;
register char c;
register
f(register unsigned m, register long n)
{
register int i;
}
register
4.8 Block Structure
any
if (n > 0) {
int i; /* declare a new i */
for (i = 0; i < n; i++)
}
i if i
i
static
85
int x;
int y;
f(double x)
{
double y;
}
f x
double f int
y
4.9 Initialization
int x = 1;
char squote = '\'';
long day = 1000L * 60L * 60L * 24L; /* milliseconds/day */
int binsearch(int x, int v[], int n)
{
int low = 0;
int high = n - 1;
int mid;
}
86
int low, high, mid;
low = 0;
high = n - 1;
days
int days[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
char pattern[] = "ould";
char pattern[] = { 'o', 'u', 'l', 'd', '\0' };
'\0'
4.10 Recursion
itoa printd
87
#include <stdio.h>
/* printd: print n in decimal */
void printd(int n)
{
if (n < 0) {
putchar('-');
n = -n;
}
if (n / 10)
printd(n / 10);
putchar(n % 10 + '0');
}
printd(123)
printd n = 123 12 printd
1 printd 1
printd 2
3
/* qsort: sort v[left]...v[right] into increasing order */
void qsort(int v[], int left, int right)
{
int i, last;
void swap(int v[], int i, int j);
if (left >= right) /* do nothing if array contains */
return; /* fewer than two elements */
swap(v, left, (left + right)/2); /* move partition elem */
last = left; /* to v[0] */
for (i = left+1; i <= right; i++) /* partition */
if (v[i] < v[left])
swap(v, ++last, i);
swap(v, left, last); /* restore partition elem */
qsort(v, left, last-1);
qsort(v, last+1, right);
}
swap
qsort
88
/* swap: interchange v[i] and v[j] */
void swap(int v[], int i, int j)
{
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
qsort
Exercise 4-12 printd itoa
□
Exercise 4-13 reverse(s)
s □
4.11 The C Preprocessor
#include
#define
4.11.1 File Inclusion
#define
#include "lename"
#include <lename>
lename lename
89
< >
#include
#include
#define extern
<stdio.h>
#include
4.11.2 Macro Substitution
#define name replacement text
name replacement text
#define
\
#define
YES
printf("YES") YESMAN
#define forever for (;;) /* infinite loop */
forever
max
#define max(A, B) ((A) > (B) ? (A) : (B))
max
A B
x = max(p+q, r+s);
x = ((p+q) > (r+s) ? (p+q) : (r+s));
90
max
max
max(i++, j++) /* WRONG */
#define square(x) x * x /* WRONG */
square(z+1)
<stdio.h> getchar putchar
<ctype.h>
#undef
#undef getchar
int getchar(void) { ... }
#
#define dprint(expr) printf(#expr " = %g\n", expr)
dprint(x/y);
printf("x/y" " = %g\n", x/y);
printf("x/y = %g\n", x/y);
" \" \ \\
##
## ##
paste
91
#define paste(front, back) front ## back
paste(name, 1) name1
##
Exercise 4-14 swap(t,x,y)
t □
4.11.3 Conditional Inclusion
#if
sizeof enum
#endif #elif #else
#elif else if defined() #if
name
hdr.h
#if !defined(HDR)
#define HDR
/* contents of hdr.h go here */
#endif
hdr.h HDR
#endif
SYSTEM
#if SYSTEM == SYSV
#define HDR "sysv.h"
#elif SYSTEM == BSD
#define HDR "bsd.h"
#elif SYSTEM == MSDOS
#define HDR "msdos.h"
#else
#define HDR "default.h"
#endif
#include HDR
92
#ifdef #ifndef
#if
#ifndef HDR
#define HDR
/* contents of hdr.h go here */
#endif
CHAPTER 5: Pointers and Arrays
goto
void *
void char *
5.1 Pointers and Addresses
char
short long
c char p
...
...
...
p:
c:
&
94
p = &c;
c p p c &
register
* indirection dereferencing
x
y ip int
& *
int x = 1, y = 2, z[10];
int *ip; /* ip is a pointer to int */
ip = &x; /* ip now points to x */
y = *ip; /* y is now 1 */
*ip = 0; /* x is now 0 */
ip = &z[0]; /* ip now points to z[0] */
x y z
ip
int *ip;
*ip int
double *dp, atof(char *);
*dp atof(s) double
atof char
void
ip x *ip x
*ip = *ip + 10;
*ip
* &
y = *ip + 1
ip y
*ip += 1
ip
95
++*ip
(*ip)++
ip
* ++
iq int
iq = ip
ip iq iq ip
5.2 Pointers and Function Arguments
swap
swap(a, b);
swap
void swap(int x, int y) /* WRONG */
{
int temp;
temp = x;
x = y;
y = temp;
}
swap a b
copies a b
point-
ers
swap(&a, &b);
& &a a
swap
96
void swap(int *px, int *py) /* interchange *px and *py */
{
int temp;
temp = *px;
*px = *py;
*py = temp;
}
getint
getint
EOF
getint
scanf
getint
int n, array[SIZE], getint(int *);
for (n = 0; n < SIZE && getint(&array[n]) != EOF; n++)
;
array[n] n
array[n] getint
getint
97
getint EOF
#include <ctype.h>
int getch(void);
void ungetch(int);
/* getint: get next integer from input into *pn */
int getint(int *pn)
{
int c, sign;
while (isspace(c = getch())) /* skip white space */
;
if (!isdigit(c) && c != EOF && c != '+' && c != '-') {
ungetch(c); /* it's not a number */
return 0;
}
sign = (c == '-') ? -1 : 1;
if (c == '+' || c == '-')
c = getch();
for (*pn = 0; isdigit(c); c = getch())
*pn = 10 * *pn + (c - '0');
*pn *= sign;
if (c != EOF)
ungetch(c);
return c;
}
getint *pn int
getch ungetch
Exercise 5-1 getint + -
□
Exercise 5-2 getfloat getint
getfloat □
5.3 Pointers and Arrays
98
int a[10];
a
a[0] a[1] a[9]
a[i] i pa
int *pa;
pa = &a[0];
pa
a
pa
a[0]
x = *pa;
a[0] x
pa pa+1
pa+i i pa pa-i i
pa a[0]
*(pa+1)
a[1] pa+i a[i] *(pa+i)
a[i]
a
pa+1 pa+i i
pa
99
pa = &a[0];
pa a
pa=&a[0]
pa = a;
a[i] *(a+i) a[i] *(a+i)
&
&a[i] a+i a+i
i a
pa pa[i]
*(pa+i)
pa=a pa++
a=pa a++
strlen
/* strlen: return length of string s */
int strlen(char *s)
{
int n;
for (n = 0; *s != '\0'; s++)
n++;
return n;
}
s s++
strlen
strlen
strlen("hello, world"); /* string constant */
strlen(array); /* char array[100]; */
strlen(ptr); /* char *ptr; */
100
char s[];
char *s;
a
f(&a[2])
f(a+2)
f a[2]
f
f(int arr[]) { ... }
f(int *arr) { ... }
f
p[−1] p[−2]
p[0]
5.4 Address Arithmetic
p p++ p
p+=i i
alloc(n) p n
alloc
afree(p)
101
afree
alloc
alloc afree
malloc free
alloc
allocbuf alloc afree
static
alloc afree
malloc
allocbuf
allocp
alloc n
allocbuf alloc allocp
n
alloc afree(p) allocp p p
allocbuf
#define ALLOCSIZE 10000 /* size of available space */
static char allocbuf[ALLOCSIZE]; /* storage for alloc */
static char *allocp = allocbuf; /* next free position */
char *alloc(int n) /* return pointer to n characters */
{
if (allocbuf + ALLOCSIZE - allocp >= n) { /* it fits */
allocp += n;
return allocp - n; /* old p */
} else /* not enough room */
return 0;
}
102
void afree(char *p) /* free storage pointed to by p */
{
if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
allocp = p;
}
static char *allocp = allocbuf;
allocp
allocbuf
static char *allocp = &allocbuf[0];
is
if (allocbuf + ALLOCSIZE - allocp >= n) { /* it fits */
n
allocp allocbuf
alloc
alloc
NULL
NULL <stdio.h> NULL
if (allocbuf + ALLOCSIZE - allocp >= n) { /* it fits */
if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
p q
== != < >=
p < q
p q
103
p + n
n p
p n
p p
int int
p q
p<q q-p+1 p q
strlen
/* strlen: return length of string s */
int strlen(char *s)
{
char *p = s;
while (*p != '\0')
p++;
return p - s;
}
p s
while
'\0' p p++ p
p-s
int <stddef.h> ptrdiff_t
size_t
strlen size_t
sizeof
float
char p float p++
float alloc
float char char float
alloc afree
float double
void *
104
5.5 Character Pointers and Functions
string constant
"I am a string"
'\0'
printf("hello, world\n");
printf
pmessage
char *pmessage;
pmessage = "now is the time";
pmessage
char amessage[] = "now is the time"; /* an array */
char *pmessage = "now is the time"; /* a pointer */
amessage
'\0'
amessage
pmessage
strcpy(s,t) t s
s=t
105
/* strcpy: copy t to s; array subscript version */
void strcpy(char *s, char *t)
{
int i;
i = 0;
while ((s[i] = t[i]) != '\0')
i++;
}
strcpy
/* strcpy: copy t to s; pointer version 1 */
void strcpy(char *s, char *t)
{
while ((*s = *t) != '\0') {
s++;
t++;
}
}
strcpy s t
'\0'
t s
strcpy
/* strcpy: copy t to s; pointer version 2 */
void strcpy(char *s, char *t)
{
while ((*s++ = *t++) != '\0')
;
}
s
t
*t++ t t ++
t
s s
'\0'
t s
'\0'
'\0'
106
/* strcpy: copy t to s; pointer version 3 */
void strcpy(char *s, char *t)
{
while (*s++ = *t++)
;
}
strcpy <string.h>
strcmp(s,t)
s t s
t
s t
/* strcmp: return <0 if s<t, 0 if s==t, >0 if s>t */
int strcmp(char *s, char *t)
{
int i;
for (i = 0; s[i] == t[i]; i++)
if (s[i] == '\0')
return 0;
return s[i] - t[i];
}
strcmp
/* strcmp: return <0 if s<t, 0 if s==t, >0 if s>t */
int strcmp(char *s, char *t)
{
for ( ; *s == *t; s++, t++)
if (*s == '\0')
return 0;
return *s - *t;
}
++ --
* ++ --
*--p
p p
*p++ = val; /* push val onto stack */
val = *--p; /* pop top of stack into val */
107
<string.h>
Exercise 5-3 strcat
strcat(s,t) t s □
Exercise 5-4 strend(s,t) t
s □
Exercise 5-5 strncpy strncat
strncmp n
strncpy(s,t,n) n t s
□
Exercise 5-6
getline
atoi itoa
reverse strindex getop □
5.6 Pointer Arrays; Pointers to Pointers
sort
strcmp
108
read all the lines of input
sort them
print them in order
−1
#include <stdio.h>
#include <string.h>
#define MAXLINES 5000 /* max #lines to be sorted */
char *lineptr[MAXLINES]; /* pointers to text lines */
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void qsort(char *lineptr[], int left, int right);
/* sort input lines */
main()
{
int nlines; /* number of input lines read */
if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
qsort(lineptr, 0, nlines-1);
writelines(lineptr, nlines);
return 0;
} else {
printf("error: input too big to sort\n");
return 1;
}
}
109
#define MAXLEN 1000 /* max length of any input line */
int getline(char *, int);
char *alloc(int);
/* readlines: read input lines */
int readlines(char *lineptr[], int maxlines)
{
int len, nlines;
char *p, line[MAXLEN];
nlines = 0;
while ((len = getline(line, MAXLEN)) > 0)
if (nlines >= maxlines || (p = alloc(len)) ==
NULL)
return -1;
else {
line[len-1] = '\0'; /* delete newline */
strcpy(p, line);
lineptr[nlines++] = p;
}
return nlines;
}
/* writelines: write output lines */
void writelines(char *lineptr[], int nlines)
{
int i;
for (i = 0; i < nlines; i++)
printf("%s\n", lineptr[i]);
}
getline
lineptr
char *lineptr[MAXLINES]
lineptr MAXLINES
char lineptr[i] *lineptr[i]
i
lineptr
writelines
/* writelines: write output lines */
void writelines(char *lineptr[], int nlines)
{
while (nlines-- > 0)
printf("%s\n", *lineptr++);
}
110
*lineptr
nlines
strcmp
/* qsort: sort v[left]...v[right] into increasing order */
void qsort(char *v[], int left, int right)
{
int i, last;
void swap(char *v[], int i, int j);
if (left >= right) /* do nothing if array contains */
return; /* fewer than two elements */
swap(v, left, (left + right)/2);
last = left;
for (i = left+1; i <= right; i++)
if (strcmp(v[i], v[left]) < 0)
swap(v, ++last, i);
swap(v, left, last);
qsort(v, left, last-1);
qsort(v, last+1, right);
}
void swap(int *px, int *py) /* interchange *px and *py */
{
int temp;
temp = *px;
*px = *py;
*py = temp;
}
v lineptr temp
Exercise 5-7 readlines main
alloc
□
5.7 Multi-dimensional Arrays
111
day_of_year
month_day
month_day(1988, 60, &m, &d)
m 2 d
static char daytab[2][13] = {
{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
/* day_of_year: set day of year from month & day */
int day_of_year(int year, int month, int day)
{
int i, leap;
leap = year%4 == 0 && year%100 != 0 || year%400 == 0;
for (i = 1; i < month; i++)
day += daytab[leap][i];
return day;
}
/* month_day: set month, day from day of year */
void month_day(int year, int yearday, int *pmonth, int
*pday)
{
int i, leap;
leap = year%4 == 0 && year%100 != 0 || year%400 == 0;
for (i = 1; yearday > daytab[leap][i]; i++)
yearday -= daytab[leap][i];
*pmonth = i;
*pday = yearday;
}
leap
daytab
112
daytab day_of_year month_day
char char
daytab
daytab[i][j] /* [row][col] */
daytab[i,j] /* WRONG */
daytab
int
int daytab
f f
f(int daytab[2][13]) { ... }
f(int daytab[][13]) { ... }
f(int (*daytab)[13]) { ... }
[ ] *
int *daytab[13]
Exercise 5-8 day_of_year month_day
□
113
5.8 Initialization of Pointer Arrays
month_name(n)
n
static month_name
/* month_name: return name of n-th month */
char *month_name(int n)
{
static char *name[] = {
"Illegal month",
"January", "February", "March",
"April", "May", "June",
"July", "August", "September",
"October", "November", "December"
};
return (n < 1 || n > 12) ? name[0] : name[n];
}
name
lineptr
i
name[i]
name
5.9 Pointers vs. Multi-dimensional Arrays
name
int a[10][20];
int *b[10];
a[3][4] b[3][4]
int a int
a[][] b
b
int
114
b
month_name
char *name[] = { "Illegal month", "Jan, "Feb", "Mar" };
char aname[][15] = { "Illegal month", "Jan", "Feb", "Mar" };
Exercise 5-9 day_of_year month_day
□
5.10 Command-line Arguments
main
argc
argv
echo
echo hello, world
hello, world
115
argv[0]
argc argc
argc argv[0] argv[1]
argv[2] "echo" "hello, " "world"
argv[1] argv[argc−1]
argv[argc]
echo argv
#include <stdio.h>
/* echo command-line arguments; 1st version */
main(int argc, char *argv[])
{
int i;
for (i = 1; i < argc; i++)
printf("%s%s", argv[i], (i < argc-1) ? " " : "");
printf("\n");
return 0;
}
argv
argv
char argc
#include <stdio.h>
/* echo command-line arguments; 2nd version */
main(int argc, char *argv[])
{
while (--argc > 0)
printf("%s%s", *++argv, (argc > 1) ? " " : "");
printf("\n");
return 0;
}
argv
++argv argv[1]
argv[0]
*argv argc
printf
116
printf((argc > 1) ? "%s " : "%s", *++argv);
printf
grep
#include <stdio.h>
#include <string.h>
#define MAXLINE 1000
int getline(char *line, int max);
/* find: print lines that match pattern from 1st arg */
main(int argc, char *argv[])
{
char line[MAXLINE];
int found = 0;
if (argc != 2)
printf("Usage: find pattern\n");
else
while (getline(line, MAXLINE) > 0)
if (strstr(line, argv[1]) != NULL) {
printf("%s", line);
found++;
}
return found;
}
strstr(s,t)
t s NULL
<string.h>
except
-x -n
find -x -n pattern
117
find -nx pattern
#include <stdio.h>
#include <string.h>
#define MAXLINE 1000
int getline(char *line, int max);
/* find: print lines that match pattern from 1st arg */
main(int argc, char *argv[])
{
char line[MAXLINE];
long lineno = 0;
int c, except = 0, number = 0, found = 0;
while (--argc > 0 && (*++argv)[0] == '-')
while (c = *++argv[0])
switch (c) {
case 'x':
except = 1;
break;
case 'n':
number = 1;
break;
default:
printf("find: illegal option %c\n", c);
argc = 0;
found = -1;
break;
}
if (argc != 1)
printf("Usage: find -x -n pattern\n");
else
while (getline(line, MAXLINE) > 0) {
lineno++;
if ((strstr(line, *argv) != NULL) != except) {
if (number)
printf("%ld:", lineno);
printf("%s", line);
found++;
}
}
return found;
}
argc argv
argc
argv argc
*argv *++argv
(*[0]
118
**++argv [] * ++
*++(argv[0])
*++argv[0] argv[0]
Exercise 5-10 expr
expr 2 3 4 + *
□
Exercise 5-11 entab detab
□
Exercise 5-12 entab detab
entab -m +n
n m
□
Exercise 5-13 tail n
n
tail -n
n
n
□
5.11 Pointers to Functions
-n
119
strcmp
numcmp
strcmp
main
qsort
#include <stdio.h>
#include <string.h>
#define MAXLINES 5000 /* max #lines to be sorted */
char *lineptr[MAXLINES]; /* pointers to text lines */
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void qsort(void *lineptr[], int left, int right,
int (*comp)(void *, void *));
int numcmp(char *, char *);
/* sort input lines */
main(int argc, char *argv[])
{
int nlines; /* number of input lines read */
int numeric = 0; /* 1 if numeric sort */
if (argc > 1 && strcmp(argv[1], "-n") == 0)
numeric = 1;
if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
qsort((void **) lineptr, 0, nlines-1,
(int (*)(void*,void*))(numeric ? numcmp : strcmp));
writelines(lineptr, nlines);
return 0;
} else {
printf("input too big to sort\n");
return 1;
}
}
qsort strcmp numcmp
&
120
qsort
qsort
void *
void * qsort
void *
/* qsort: sort v[left]...v[right] into increasing order */
void qsort(char *v[], int left, int right)
{
int i, last;
void swap(char *v[], int i, int j);
if (left >= right) /* do nothing if array contains */
return; /* fewer than two elements */
swap(v, left, (left + right)/2);
last = left;
for (i = left+1; i <= right; i++)
if (strcmp(v[i], v[left]) < 0)
swap(v, ++last, i);
swap(v, left, last);
qsort(v, left, last-1);
qsort(v, last+1, right);
}
qsort
int (*comp)(void *, void *)
comp void *
int
comp
if ((*comp)(v[i], v[left]) < 0)
comp *comp
(*comp)(v[i], v[left])
int *comp(void *, void *) /* WRONG */
comp int
strcmp
numcmp
atof
121
#include <stdlib.h>
/* numcmp: compare s1 and s2 numerically */
int numcmp(char *s1, char *s2)
{
double v1, v2;
v1 = atof(s1);
v2 = atof(s2);
if (v1 < v2)
return -1;
else if (v1 > v2)
return 1;
else
return 0;
}
swap
void *
/* swap: interchange v[i] and v[j] */
void swap(char *v[], int i, int j)
{
char *temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
Exercise 5-14 -r
-r -n □
Exercise 5-15 -f
a A
□
Exercise 5-16 -d
-f □
Exercise 5-17
-df -n
□
122
5.12 Complicated Declarations
int *f(); /* f: function returning pointer to int */
int (*pf)(); /* pf: pointer to function returning int */
*
()
typedef
dcl
char **argv
argv: pointer to pointer to char
int (*daytab)[13]
daytab: pointer to array[13] of int
int *daytab[13]
daytab: array[13] of pointer to int
void *comp()
comp: function returning pointer to void
void (*comp)()
comp: pointer to function returning void
char (*(*x())[])()
x: function returning pointer to array[] of
pointer to function returning char
char (*(*x[3])())[5]
x: array[3] of pointer to function returning
pointer to array[5] of char
dcl
dcl: optional *’s direct-dcl
direct-dcl: name
(dcl)
direct-dcl()
direct-dcl[optional size]
123
dcl direct-dcl * direct-dcl
dcl direct-dcl direct-dcl
(*pfa[])()
pfa name direct-dcl pfa[]
direct-dcl *pfa[] dcl (* direct-dcl
(* direct-dcl dcl
direct-dcl dir-dcl
dcl dcl dirdcl
/* dcl: parse a declarator */
void dcl(void)
{
int ns;
for (ns = 0; gettoken() == '*'; ) /* count *'s */
ns++;
dirdcl();
while (ns-- > 0)
strcat(out, " pointer to");
}
124
/* dirdcl: parse a direct declarator */
void dirdcl(void)
{
int type;
if (tokentype == '(') { /* ( dcl ) */
dcl();
if (tokentype != ')')
printf("error: missing )\n");
} else if (tokentype == NAME) /* variable name */
strcpy(name, token);
else
printf("error: expected name or (dcl)\n");
while ((type=gettoken()) == PARENS || type ==
BRACKETS)
if (type == PARENS)
strcat(out, " function returning");
else {
strcat(out, " array");
strcat(out, token);
strcat(out, " of");
}
}
dcl
char int
const
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAXTOKEN 100
enum { NAME, PARENS, BRACKETS };
void dcl(void);
void dirdcl(void);
int gettoken(void);
int tokentype; /* type of last token */
char token[MAXTOKEN]; /* last token string */
char name[MAXTOKEN]; /* identifier name */
char datatype[MAXTOKEN]; /* data type = char, int, etc. */
char out[1000]; /* output string */
125
main() /* convert declaration to words */
{
while (gettoken() != EOF) { /* 1st token on line */
strcpy(datatype, token); /* is the datatype */
out[0] = '\0';
dcl(); /* parse rest of line */
if (tokentype != '\n')
printf("syntax error\n");
printf("%s: %s %s\n", name, out, datatype);
}
return 0;
}
gettoken
int gettoken(void) /* return next token */
{
int c, getch(void);
void ungetch(int);
char *p = token;
while ((c = getch()) == ' ' || c == '\t')
;
if (c == '(') {
if ((c = getch()) == ')') {
strcpy(token, "()");
return tokentype = PARENS;
} else {
ungetch(c);
return tokentype = '(';
}
} else if (c == '[') {
for (*p++ = c; (*p++ = getch()) != ']'; )
;
*p = '\0';
return tokentype = BRACKETS;
} else if (isalpha(c)) {
for (*p++ = c; isalnum(c = getch()); )
*p++ = c;
*p = '\0';
ungetch(c);
return tokentype = NAME;
} else
return tokentype = c;
}
getch ungetch
undcl
126
x
char
x () * [] * () char
char (*(*x())[])()
gettoken undcl
dcl
/* undcl: convert word description to declaration */
main()
{
int type;
char temp[MAXTOKEN];
while (gettoken() != EOF) {
strcpy(out, token);
while ((type = gettoken()) != '\n')
if (type == PARENS || type == BRACKETS)
strcat(out, token);
else if (type == '*') {
sprintf(temp, "(*%s)", out);
strcpy(out, temp);
} else if (type == NAME) {
sprintf(temp, "%s %s", token, out);
strcpy(out, temp);
} else
printf("invalid input at %s\n", token);
printf("%s\n", out);
}
return 0;
}
Exercise 5-18 dcl □
Exercise 5-19 undcl
□
Exercise 5-20 dcl
const □
CHAPTER 6: Structures
6.1 Basics of Structures
x y
(0,0)
(4,3)
x
y
128
struct point {
int x;
int y;
};
struct
struct point
members.
struct
struct { ... } x, y, z;
int x, y, z;
x y z
point
struct point pt;
pt struct point
struct point maxpt = { 320, 200 };
structure-name . member
"."
pt
129
printf("%d,%d", pt.x, pt.y);
pt
double dist, sqrt(double);
dist = sqrt((double)pt.x * pt.x + (double)pt.y * pt.y);
pt1
x
y
pt2
struct rect {
struct point pt1;
struct point pt2;
};
rect point screen
struct rect screen;
screen.pt1.x
x pt1 screen
6.2 Structures and Functions
&
makepoint point
130
/* makepoint: make a point from x and y components */
struct point makepoint(int x, int y)
{
struct point temp;
temp.x = x;
temp.y = y;
return temp;
}
makepoint
struct rect screen;
struct point middle;
struct point makepoint(int, int);
screen.pt1 = makepoint(0, 0);
screen.pt2 = makepoint(XMAX, YMAX);
middle = makepoint((screen.pt1.x + screen.pt2.x)/2,
(screen.pt1.y + screen.pt2.y)/2);
/* addpoint: add two points */
struct point addpoint(struct point p1, struct point p2)
{
p1.x += p2.x;
p1.y += p2.y;
return p1;
}
p1
ptinrect
/* ptinrect: return 1 if p in r, 0 if not */
int ptinrect(struct point p, struct rect r)
{
return p.x >= r.pt1.x && p.x < r.pt2.x
&& p.y >= r.pt1.y && p.y < r.pt2.y;
}
pt1
pt2
131
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
/* canonrect: canonicalize coordinates of rectangle */
struct rect canonrect(struct rect r)
{
struct rect temp;
temp.pt1.x = min(r.pt1.x, r.pt2.x);
temp.pt1.y = min(r.pt1.y, r.pt2.y);
temp.pt2.x = max(r.pt1.x, r.pt2.x);
temp.pt2.y = max(r.pt1.y, r.pt2.y);
return temp;
}
struct point *pp;
pp struct point pp
point
*
pp (* (*
pp
struct point origin, *pp;
pp = &origin;
printf("origin is (%d,%d)\n", (*pp).x, (*pp).y);
(*
.
*
*
pp.x
*
(pp.x)
x
p
p->member-of-structure
->
>
printf("origin is (%d,%d)\n", pp->x, pp->y);
. ->
struct rect r, *rp = &r;
r.pt1.x
rp->pt1.x
(r.pt1).x
(rp->pt1).x
132
. -> ()
[]
struct {
int len;
char *str;
} *p;
++p->len
len p ++(p->len)
(++p)->len p
len (p++)->len p
*
p->str str
*
p->str++
str
*
s++ (*
str
*
p++->str p
str
6.3 Arrays of Structures
keyword
keycount
char *keyword[NKEYS];
int keycount[NKEYS];
char *word;
int count;
struct key {
char *word;
int count;
} keytab[NKEYS];
key keytab
133
struct key {
char *word;
int count;
};
struct key keytab[NKEYS];
keytab
struct key {
char *word;
int count;
} keytab[] = {
"auto", 0,
"break", 0,
"case", 0,
"char", 0,
"const", 0,
"continue", 0,
"default", 0,
/* ... */
"unsigned", 0,
"void", 0,
"volatile", 0,
"while", 0
};
{ "auto", 0 },
{ "break", 0 },
{ "case", 0 },
keytab []
keytab
getword
keytab
134
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
int getword(char *, int);
int binsearch(char *, struct key *, int);
/* count C keywords */
main()
{
int n;
char word[MAXWORD];
while (getword(word, MAXWORD) != EOF)
if (isalpha(word[0]))
if ((n = binsearch(word, keytab, NKEYS)) >= 0)
keytab[n].count++;
for (n = 0; n < NKEYS; n++)
if (keytab[n].count > 0)
printf("%4d %s\n",
keytab[n].count, keytab[n].word);
return 0;
}
/* binsearch: find word in tab[0]...tab[n-1] */
int binsearch(char *word, struct key tab[], int n)
{
int cond;
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high) {
mid = (low+high) / 2;
if ((cond = strcmp(word, tab[mid].word)) < 0)
high = mid - 1;
else if (cond > 0)
low = mid + 1;
else
return mid;
}
return -1;
}
getword
getword
NKEYS keytab
135
keytab
size of keytab / size of struct key
sizeof
sizeof object
sizeof(type name)
sizeof size_t
<stddef.h>
int double
#define
NKEYS
#define NKEYS (sizeof keytab / sizeof(struct key))
#define NKEYS (sizeof keytab / sizeof keytab[0])
sizeof #if
#define
getword getword
getword
EOF
136
/* getword: get next word or character from input */
int getword(char *word, int lim)
{
int c, getch(void);
void ungetch(int);
char *w = word;
while (isspace(c = getch()))
;
if (c != EOF)
*w++ = c;
if (!isalpha(c)) {
*w = '\0';
return c;
}
for ( ; --lim > 0; w++)
if (!isalnum(*w = getch())) {
ungetch(*w);
break;
}
*w = '\0';
return word[0];
}
getword getch ungetch
getword
ungetch
getword isspace isalpha
isalnum
<ctype.h>
Exercise 6-1 getword
□
6.4 Pointers to Structures
keytab main
binsearch
137
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
int getword(char *, int);
struct key *binsearch(char *, struct key *, int);
/* count C keywords; pointer version */
main()
{
char word[MAXWORD];
struct key *p;
while (getword(word, MAXWORD) != EOF)
if (isalpha(word[0]))
if ((p=binsearch(word, keytab, NKEYS)) !=
NULL)
p->count++;
for (p = keytab; p < keytab + NKEYS; p++)
if (p->count > 0)
printf("%4d %s\n", p->count, p->word);
return 0;
}
/* binsearch: find word in tab[0]...tab[n-1] */
struct key *binsearch(char *word, struct key *tab, int n)
{
int cond;
struct key *low = &tab[0];
struct key *high = &tab[n];
struct key *mid;
while (low < high) {
mid = low + (high-low) / 2;
if ((cond = strcmp(word, mid->word)) < 0)
high = mid;
else if (cond > 0)
low = mid + 1;
else
return mid;
}
return NULL;
}
binsearch struct key
binsearch
binsearch NULL
keytab
binsearch
138
low high
mid = (low+high) / 2; /* WRONG */
high-low
mid = low + (high-low) / 2;
mid low high
&tab[−1] &tab[n]
tab
&tab[n]
main
for (p = keytab; p < keytab + NKEYS; p++)
p p
p++ p
char
int
struct {
char c;
int i;
};
sizeof
struct key *binsearch(char *word, struct key *tab, int n)
struct key *
binsearch(char *word, struct key *tab, int n)
139
6.5 Self-referential Structures
all
binary tree.
140
struct tnode { /* the tree node: */
char *word; /* points to the text */
int count; /* number of occurrences */
struct tnode *left; /* left child */
struct tnode *right; /* right child */
};
struct tnode *left;
left tnode tnode
struct t {
...
struct s *p; /* p points to an s */
};
struct s {
...
struct t *q; /* q points to a t */
};
getword
getword addtree
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);
/* word frequency count */
main()
{
struct tnode *root;
char word[MAXWORD];
root = NULL;
while (getword(word, MAXWORD) != EOF)
if (isalpha(word[0]))
root = addtree(root, word);
treeprint(root);
return 0;
}
141
addtree main
addtree
addtree
struct tnode *talloc(void);
char *strdup(char *);
/* addtree: add a node with w, at or below p */
struct tnode *addtree(struct tnode *p, char *w)
{
int cond;
if (p == NULL) { /* a new word has arrived */
p = talloc(); /* make a new node */
p->word = strdup(w);
p->count = 1;
p->left = p->right = NULL;
} else if ((cond = strcmp(w, p->word)) == 0)
p->count++; /* repeated word */
else if (cond < 0) /* less than into left subtree */
p->left = addtree(p->left, w);
else /* greater than into right subtree */
p->right = addtree(p->right, w);
return p;
}
talloc
strdup
strdup talloc
treeprint
treeprint
142
/* treeprint: in-order print of tree p */
void treeprint(struct tnode *p)
{
if (p != NULL) {
treeprint(p->left);
printf("%4d %s\n", p->count, p->word);
treeprint(p->right);
}
}
char
struct tnode
all alloc
malloc
malloc
malloc
malloc void
malloc
<stdlib.h> talloc
#include <stdlib.h>
/* talloc: make a tnode */
struct tnode *talloc(void)
{
return (struct tnode *) malloc(sizeof(struct tnode));
}
strdup
malloc
143
char *strdup(char *s) /* make a duplicate of s */
{
char *p;
p = (char *) malloc(strlen(s)+1); /* +1 for '\0' */
if (p != NULL)
strcpy(p, s);
return p;
}
malloc NULL strdup
malloc free
Exercise 6-2
□
Exercise 6-3
□
Exercise 6-4
□
6.6 Table Lookup
#define
#define IN 1
IN 1
IN
state = IN;
1
install(s,t) s t s
t lookup(s) s
NULL
144
NULL
0
0
0
0
name
defn
name
defn
0
struct nlist { /* table entry: */
struct nlist *next; /* next entry in chain */
char *name; /* defined name */
char *defn; /* replacement text */
};
#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* pointer table */
lookup install
/* hash: form hash value for string s */
unsigned hash(char *s)
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
hashtab
lookup lookup
NULL
145
/* lookup: look for s in hashtab */
struct nlist *lookup(char *s)
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
if (strcmp(s, np->name) == 0)
return np; /* found */
return NULL; /* not found */
}
for lookup
for (ptr = head; ptr != NULL; ptr = ptr->next)
...
install lookup
install NULL
struct nlist *lookup(char *);
char *strdup(char *);
/* install: put (name, defn) in hashtab */
struct nlist *install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL) { /* not found */
np = (struct nlist *) malloc(sizeof(*np));
if (np == NULL || (np->name = strdup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
} else /* already there */
free((void *) np->defn); /* free previous defn */
if ((np->defn = strdup(defn)) == NULL)
return NULL;
return np;
}
Exercise 6-5 undef
lookup install □
Exercise 6-6 #define
getch ungetch □
146
6.7 Typedef
typedef
typedef int Length;
Length int Length
int
Length len, maxlen;
Length *lengths[];
typedef char *String;
String char *
String p, lineptr[MAXLINES], alloc(int);
int strcmp(String, String);
p = (String) malloc(100);
typedef
typedef typedef
extern static
typedef
typedef
typedef struct tnode *Treeptr;
typedef struct tnode { /* the tree node: */
char *word; /* points to the text */
int count; /* number of occurrences */
Treeptr left; /* left child */
Treeptr right; /* right child */
} Treenode;
Treenode Treeptr
talloc
Treeptr talloc(void)
{
return (Treeptr) malloc(sizeof(Treenode));
}
typedef
typedef #define
147
typedef int (*PFI)(char *, char *);
PFI char *
int
PFI strcmp, numcmp;
typedef
typedef
typedef
typedef
short int long
size_t ptrdiff_t
typedef
Treeptr
6.8 Unions
union
int float
union u_tag {
int ival;
float fval;
char *sval;
} u;
u
u
148
union-name . member
union-pointer->member
utype
u
if (utype == INT)
printf("%d\n", u.ival);
else if (utype == FLOAT)
printf("%f\n", u.fval);
else if (utype == STRING)
printf("%s\n", u.sval);
else
printf("bad type %d in utype\n", utype);
struct {
char *name;
int flags;
int utype;
union {
int ival;
float fval;
char *sval;
} u;
} symtab[NSYM];
ival
symtab[i].u.ival
sval
*symtab[i].u.sval
symtab[i].u.sval[0]
u
149
6.9 Bit-fields
char int
#define KEYWORD 01
#define EXTERNAL 02
#define STATIC 04
enum { KEYWORD = 01, EXTERNAL = 02, STATIC = 04 };
flags |= EXTERNAL | STATIC;
EXTERNAL STATIC flags
flags &= ~(EXTERNAL | STATIC);
if ((flags &(EXTERNAL | STATIC)) == 0) ...
bit-eld eld
150
#define
struct {
unsigned int is_keyword : 1;
unsigned int is_extern : 1;
unsigned int is_static : 1;
} flags;
flags
unsigned int
flags.is_keyword flags.is_extern
flags.is_extern = flags.is_static = 1;
flags.is_extern = flags.is_static = 0;
if (flags.is_extern == 0 && flags.is_static == 0)
...
int
signed unsigned
&
CHAPTER 7: Input and Output
<stdio.h>, <string.h>
<ctype.h>
7.1 Standard Input and Output
standard input getchar
int getchar(void)
getchar EOF
EOF <stdio.h>
152
−1 EOF
< prog getchar
prog <infile
prog infile
prog
"<infile" argv
otherprog | prog
otherprog prog
otherprog prog
int putchar(int)
putchar(c) c standard output
putchar EOF
>filename
prog putchar
prog >outfile
outfile
prog | anotherprog
prog anotherprog
printf
putchar printf
#include <stdio.h>
< >
/usr/include
getchar putchar
printf
lower
153
#include <stdio.h>
#include <ctype.h>
main() /* lower: convert input to lower case */
{
int c;
while ((c = getchar()) != EOF)
putchar(tolower(c));
return 0;
}
tolower <ctype.h>
getchar putchar <stdio.h> tolower
<ctype.h>
<ctype.h>
Exercise 7-1
argv[0] □
7.2 Formatted Output—Printf
printf
printf
int printf(char *format, arg
1
, arg
2
, ...)
printf
format
printf %
%
154
h short l long
%
d,i int
o int
x,X int 0x
0X abcdef ABCDEF
u int
c int
s char * '\0'
f double m.dddddd d
e, E double m.dddddde±xx m.ddddddE±xx
d
g, G double %e %E
%f
p void *
% %
*
int
max s
printf("%.*s", max, s);
:%s: :hello, world:
:%10s: :hello, world:
:%.10s: :hello, wor:
:%-10s: :hello, world:
:%.15s: :hello, world:
:%-15s: :hello, world :
:%15.10s: : hello, wor:
:%-15.10s: :hello, wor :
155
printf
printf(s); /* FAILS if s contains % */
printf("%s", s); /* SAFE */
sprintf printf
int sprintf(char *string, char *format, arg
1
, arg
2
, ...)
sprintf arg
1
arg
2
format
string
string
Exercise 7-2
□
7.3 Variable-length Argument Lists
printf
minprintf
printf
printf
int printf(char *fmt, ...)
...
...
minprintf
void minprintf(char *fmt, ...)
printf
minprintf
<stdarg.h>
va_list
minprintf ap
va_start ap
ap
va_start
156
va_arg ap va_arg
va_end
printf
#include <stdarg.h>
/* minprintf: minimal printf with variable argument list */
void minprintf(char *fmt, ...)
{
va_list ap; /* points to each unnamed arg in turn */
char *p, *sval;
int ival;
double dval;
va_start(ap, fmt); /* make ap point to 1st unnamed arg */
for (p = fmt; *p; p++) {
if (*p != '%') {
putchar(*p);
continue;
}
switch (*++p) {
case 'd':
ival = va_arg(ap, int);
printf("%d", ival);
break;
case 'f':
dval = va_arg(ap, double);
printf("%f", dval);
break;
case 's':
for (sval = va_arg(ap, char *); *sval; sval++)
putchar(*sval);
break;
default:
putchar(*p);
break;
}
}
va_end(ap); /* clean up when done */
}
Exercise 7-3 minprintf printf
□
157
7.4 Formatted Input—Scanf
scanf printf
int scanf(char *format, ...)
scanf
format
each
of which must be a pointer
printf
scanf
EOF
scanf
sscanf
int sscanf(char *string, char *format, arg
1
, arg
2
, ...)
string format
arg
1
arg
2
%
%
*
h l L
*
scanf
158
d int *
i int *
0x 0X
o int *
u unsigned int *
x 0x 0X int *
c char s
%1s
s char s
'\0'
e,f,g
float *
% %
d i o u x h
short int
l long
e f g l
double float
scanf
#include <stdio.h>
main() /* rudimentary calculator */
{
double sum, v;
sum = 0;
while (scanf("%lf", &v) == 1)
printf("\t%.2f\n", sum += v);
return 0;
}
25 Dec 1988
159
scanf
int day, year;
char monthname[20];
scanf("%d %s %d", &day, monthname, &year);
& monthname
scanf
mm/dd/yy
scanf
int day, year;
char monthname[20];
scanf("%d %s %d", &day, monthname, &year);
scanf
sscanf
while (getline(line, sizeof(line)) > 0) {
if (sscanf(line, "%d %s %d", &day, monthname, &year) == 3)
printf("valid: %s\n", line); /* 25 Dec 1988 form */
else if (sscanf(line, "%d/%d/%d", &month, &day, &year) == 3)
printf("valid: %s\n", line); /* mm/dd/yy form */
else
printf("invalid: %s\n", line); /* invalid form */
}
scanf
scanf
scanf sscanf
scanf("%d", n);
scanf("%d", &n);
Exercise 7-4 scanf minprintf
□
Exercise 7-5 scanf
sscanf □
160
7.5 File Access
not
cat
cat
cat x.c y.c
x.c y.c
fopen fopen x.c y.c
le pointer
<stdio.h>
FILE
FILE *fp;
FILE *fopen(char *name, char *mode);
fp FILE fopen FILE
FILE int
typedef fopen
fopen
fp = fopen(name, mode);
fopen
mode
"r" "w"
"a"
"b"
161
fopen
NULL
getc putc getc
int getc(FILE *fp)
getc fp
EOF
putc
int putc(int c, FILE *fp)
putc c fp
EOF getchar putchar getc putc
stdin stdout stderr
<stdio.h> stdin stdout
stderr stdin stdout
getchar putchar getc putc stdin
stdout
#define getchar() getc(stdin)
#define putchar(c) putc((c), stdout)
fscanf fprintf
scanf printf
int fscanf(FILE *fp, char *format, ...)
int fprintf(FILE *fp, char *format, ...)
cat
162
#include <stdio.h>
/* cat: concatenate files, version 1 */
main(int argc, char *argv[])
{
FILE *fp;
void filecopy(FILE *, FILE *);
if (argc == 1) /* no args; copy standard input */
filecopy(stdin, stdout);
else
while (--argc > 0)
if ((fp = fopen(*++argv, "r")) == NULL) {
printf("cat: can't open %s\n", *argv);
return 1;
} else {
filecopy(fp, stdout);
fclose(fp);
}
return 0;
}
/* filecopy: copy file ifp to file ofp */
void filecopy(FILE *ifp, FILE *ofp)
{
int c;
while ((c = getc(ifp)) != EOF)
putc(c, ofp);
}
stdin stdout FILE *
not
int fclose(FILE *fp)
fopen
fopen
cat
fclose putc
fclose
stdin stdout
freopen
163
7.6 Error Handling—Stderr and Exit
cat
stderr
stdin stdout
stderr
cat
#include <stdio.h>
/* cat: concatenate files, version 2 */
main(int argc, char *argv[])
{
FILE *fp;
void filecopy(FILE *, FILE *);
char *prog = argv[0]; /* program name for errors */
if (argc == 1) /* no args; copy standard input */
filecopy(stdin, stdout);
else
while (--argc > 0)
if ((fp = fopen(*++argv, "r")) == NULL) {
fprintf(stderr, "%s: can't open %s\n",
prog, *argv);
exit(1);
} else {
filecopy(fp, stdout);
fclose(fp);
}
if (ferror(stdout)) {
fprintf(stderr, "%s: error writing stdout\n", prog);
exit(2);
}
exit(0);
}
fprintf stderr
argv[0]
exit
exit
164
exit fclose
main return expr exit exit
ferror
fp
int ferror(FILE *fp)
feof(FILE * ferror
int feof(FILE *fp)
7.7 Line Input and Output
fgets
getline
char *fgets(char *line, int maxline, FILE *fp)
fgets fp
line maxline−1
�\0� fgets line
NULL getline
fputs
int fputs(char *line, FILE *fp)
EOF
gets puts fgets fputs
stdin stdout gets �\n�
puts
fgets fputs
165
/* fgets: get at most n chars from iop */
char *fgets(char *s, int n, FILE *iop)
{
register int c;
register char *cs;
cs = s;
while (--n > 0 && (c = getc(iop)) != EOF)
if ((*cs++ = c) == '\n')
break;
*cs = '\0';
return (c == EOF && cs == s) ? NULL : s;
}
/* fputs: put string s on file iop */
int fputs(char *s, FILE *iop)
{
int c;
while (c = *s++)
putc(c, iop);
return ferror(iop) ? EOF : 0;
}
ferror fputs
EOF
getline fgets
/* getline: read a line, return length */
int getline(char *line, int max)
{
if (fgets(line, max, stdin) == NULL)
return 0;
else
return strlen(line);
}
Exercise 7-6
□
Exercise 7-7
□
Exercise 7-8
□
166
7.8 Miscellaneous Functions
7.8.1 String Operations
strlen strcpy strcat
strcmp <string.h> s t char * c
n int
strcat(s,t) t s
strncat(s,t,n) n t s
strcmp(s,t)
s < t s == t s > t
strncmp(s,t,n) strcmp n
strcpy(s,t) t s
strncpy(s,t,n) n t s
strlen(s) s
strchr(s,c) c s NULL
strrchr(s,c) c s NULL
7.8.2 Character Class Testing and Conversion
<ctype.h>
c int unsigned char
EOF int
isalpha(c) c
isupper(c) c
islower(c) c
isdigit(c) c
isalnum(c) isalpha(c) isdigit(c)
isspace(c) c
toupper(c) c
tolower(c) c
7.8.3 Ungetc
ungetch ungetc
int ungetc(int c, FILE *fp)
167
c fp c EOF
ungetc
scanf getc getchar
7.8.4 Command Execution
system(char *
s
s
system("date");
date
system
exit
7.8.5 Storage Management
malloc calloc
void *malloc(size_t n)
n NULL
void *calloc(size_t n, size_t size)
n
NULL
malloc calloc
int *ip;
ip = (int *) calloc(n, sizeof(int));
free(p) p p
malloc calloc
calloc malloc
for (p = head; p != NULL; p = p->next) /* WRONG */
free(p);
for (p = head; p != NULL; p = q) {
q = p->next;
free(p);
}
168
malloc
7.8.6 Mathematical Functions
<math.h>
double
double
sin(x) x x
cos(x) x x
atan2(y,x) yx
exp(x) e
x
log(x) e x x
log10(x) log10(x) x x
pow(x,y) x
y
sqrt(x) sqrt(x) x x ⩾
fabs(x) fabs(x) x
7.8.7 Random Number Generation
rand()
RAND_MAX <stdlib.h>
#define frand() ((double) rand() / (RAND_MAX+1.0))
srand(unsigned) rand
rand srand
Exercise 7-9 isupper
□
CHAPTER 8: The UNIX System Interface
system
calls
8.1 File Descriptors
opening
170
le descriptor.
< >
prog <infile >outfile
8.2 Low Level I/O—Read and Write
read write
read write
int n_read = read(int fd, char *buf, int n);
int n_written = write(int fd, char *buf, int n);
−1
171
#include "syscalls.h"
main() /* copy input to output */
{
char buf[BUFSIZ];
int n;
while ((n = read(0, buf, BUFSIZ)) > 0)
write(1, buf, n);
return 0;
}
syscalls.h
BUFSIZ syscalls.h
BUFSIZ read
write
read
read write
getchar putchar
getchar
#include "syscalls.h"
/* getchar: unbuffered single character input */
int getchar(void)
{
char c;
return (read(0, &c, 1) == 1) ? (unsigned char) c : EOF;
}
c char read c
unsigned char
getchar
172
#include "syscalls.h"
/* getchar: simple buffered version */
int getchar(void)
{
static char buf[BUFSIZ];
static char *bufp = buf;
static int n = 0;
if (n == 0) { /* buffer is empty */
n = read(0, buf, sizeof buf);
bufp = buf;
}
return (--n >= 0) ? (unsigned char) *bufp++ : EOF;
}
getchar <stdio.h>
#undef getchar
8.3 Open, Creat, Close, Unlink
open creat
open fopen
int open
−1
#include <fcntl.h>
int fd;
int open(char *name, int flags, int perms);
fd = open(name, flags, perms);
fopen name
flags int
O_RDONLY
O_WRONLY
O_RDWR
<fcntl.h>
<sys/file.h>
fd = open(name, O_RDONLY, 0);
173
perms open
open creat
int creat(char *name, int perms);
fd = creat(name, perms);
−1
creat
creat
creat
perms
0755
cp
#include <stdio.h>
#include <fcntl.h>
#include "syscalls.h"
#define PERMS 0666 /* RW for owner, group, others */
void error(char *, ...);
/* cp: copy f1 to f2 */
main(int argc, char *argv[])
{
int f1, f2, n;
char buf[BUFSIZ];
if (argc != 3)
error("Usage: cp from to");
if ((f1 = open(argv[1], O_RDONLY, 0)) == -1)
error("cp: can't open %s", argv[1]);
if ((f2 = creat(argv[2], PERMS)) == -1)
error("cp: can't create %s, mode %03o",
argv[2], PERMS);
while ((n = read(f1, buf, BUFSIZ)) > 0)
if (write(f2, buf, n) != n)
error("cp: write error on file %s", argv[2]);
return 0;
}
174
0666
error
printf error
printf vprintf printf
va_start vfprintf
vsprintf fprintf sprintf
#include <stdio.h>
#include <stdarg.h>
/* error: print an error message and die */
void error(char *fmt, ...)
{
va_list args;
va_start(args, fmt);
fprintf(stderr, "error: ");
vfprintf(stderr, fmt, args);
fprintf(stderr, "\n");
va_end(args);
exit(1);
}
close(int
fd)
fclose
exit
unlink(char * name
remove
Exercise 8-1 cat read write open
close
□
8.4 Random Access—Lseek
read write
175
lseek
long lseek(int fd, long offset, int origin);
fd offset
origin
origin offset
>>
"a" fopen
lseek(fd, 0L, 2);
lseek(fd, 0L, 0);
0L (long) 0 0
lseek
lseek
−1
#include "syscalls.h"
/* get: read n bytes from position pos */
int get(int fd, long pos, char *buf, int n)
{
if (lseek(fd, pos, 0) >= 0) /* get to pos */
return read(fd, buf, n);
else
return -1;
}
lseek long
−1 fseek lseek
FILE *
8.5 Example—An Implementation of Fopen and Getc
fopen getc
176
<stdio.h>
#include
<stdio.h>
#define NULL 0
#define EOF (-1)
#define BUFSIZ 1024
#define OPEN_MAX 20 /* max #files open at once */
typedef struct _iobuf {
int cnt; /* characters left */
char *ptr; /* next character position */
char *base; /* location of buffer */
int flag; /* mode of file access */
int fd; /* file descriptor */
} FILE;
extern FILE _iob[OPEN_MAX];
#define stdin (&_iob[0])
#define stdout (&_iob[1])
#define stderr (&_iob[2])
enum _flags {
_READ = 01, /* file open for reading */
_WRITE = 02, /* file open for writing */
_UNBUF = 04, /* file is unbuffered */
_EOF = 010, /* EOF has occurred on this file */
_ERR = 020 /* error occurred on this file */
};
int _fillbuf(FILE *);
int _flushbuf(int, FILE *);
#define feof(p) (((p)->flag & _EOF) != 0)
#define ferror(p) (((p)->flag & _ERR) != 0)
#define fileno(p) ((p)->fd)
#define getc(p) (--(p)->cnt >= 0 \
? (unsigned char) *(p)->ptr++ : _fillbuf(p))
#define putc(x,p) (--(p)->cnt >= 0 \
? *(p)->ptr++ = (x) : _flushbuf((x),p))
#define getchar() getc(stdin)
#define putchar(x) putc((x), stdout)
177
getc
#define
getc _fillbuf
unsigned
putc getc
_flushbuf
fopen fopen
fopen
_fillbuf
#include <fcntl.h>
#include "syscalls.h"
#define PERMS 0666 /* RW for owner, group, others */
/* fopen: open file, return file ptr */
FILE *fopen(char *name, char *mode)
{
int fd;
FILE *fp;
if (*mode != 'r' && *mode != 'w' && *mode != 'a')
return NULL;
for (fp = _iob; fp < _iob + OPEN_MAX; fp++)
if ((fp->flag & (_READ | _WRITE)) == 0)
break; /* found free slot */
if (fp >= _iob + OPEN_MAX) /* no free slots */
return NULL;
if (*mode == 'w')
fd = creat(name, PERMS);
else if (*mode == 'a') {
if ((fd = open(name, O_WRONLY, 0)) == -1)
fd = creat(name, PERMS);
lseek(fd, 0L, 2);
} else
fd = open(name, O_RDONLY, 0);
if (fd == -1) /* couldn't access name */
return NULL;
fp->fd = fd;
fp->cnt = 0;
fp->base = NULL;
fp->flag = (*mode == 'r') ? _READ : _WRITE;
return fp;
}
178
fopen
fopen "b"
"+"
getc
_fillbuf _fillbuf
EOF
_fillbuf
read
_fillbuf
#include "syscalls.h"
/* _fillbuf: allocate and fill input buffer */
int _fillbuf(FILE *fp)
{
int bufsize;
if ((fp->flag&(_READ|_EOF|_ERR)) != _READ)
return EOF;
bufsize = (fp->flag & _UNBUF) ? 1 : BUFSIZ;
if (fp->base == NULL) /* no buffer yet */
if ((fp->base = (char *) malloc(bufsize)) == NULL)
return EOF; /* can't get buffer */
fp->ptr = fp->base;
fp->cnt = read(fp->fd, fp->ptr, bufsize);
if (--fp->cnt < 0) {
if (fp->cnt == -1)
fp->flag |= _EOF;
else
fp->flag |= _ERR;
fp->cnt = 0;
return EOF;
}
return (unsigned char) *fp->ptr++;
}
_iob stdin stdout stderr
FILE _iob[OPEN_MAX] = { /* stdin, stdout, stderr: */
{ 0, (char *) 0, (char *) 0, _READ, 0 },
{ 0, (char *) 0, (char *) 0, _WRITE, 1 },
{ 0, (char *) 0, (char *) 0, _WRITE | _UNBUF, 2 }
};
flag stdin
stdout stderr
179
Exercise 8-2 fopen _fillbuf
□
Exercise 8-3 _flushbuf fflush fclose □
Exercise 8-4
int fseek(FILE *fp, long offset, int origin)
lseek fp
int fseek
fseek
□
8.6 Example—Listing Directories
about
ls
dir
ls
fsize fsize
1s
fsize
inode
Dirent opendir readdir closedir
fsize
180
Dirent
NAME_MAX
opendir DIR FILE
readdir closedir
dirent.h
#define NAME_MAX 14 /* longest filename component; */
/* system-dependent */
typedef struct { /* portable directory entry: */
long ino; /* inode number */
char name[NAME_MAX+1]; /* name + '\0' terminator */
} Dirent;
typedef struct { /* minimal DIR: no buffering, etc. */
int fd; /* file descriptor for directory */
Dirent d; /* the directory entry */
} DIR;
DIR *opendir(char *dirname);
Dirent *readdir(DIR *dfd);
void closedir(DIR *dfd);
stat
−1
char *name;
struct stat stbuf;
int stat(char *, struct stat *);
stat(name, &stbuf);
stbuf name
stat <sys/stat.h>
struct stat /* inode information returned by stat */
{
dev_t st_dev; /* device of inode */
ino_t st_ino; /* inode number */
short st_mode; /* mode bits */
short st_nlink; /* number of links to file */
short st_uid; /* �owners user id */
short st_gid; /* �owners group id */
dev_t st_rdev; /* for special files */
off_t st_size; /* file size in characters */
time_t st_atime; /* time last accessed */
time_t st_mtime; /* time last modified */
time_t st_ctime; /* time inode last changed */
};
ino_t <sys/types.h>
181
st_mode
<sys/stat.h>
#define S_IFMT 0160000 /* type of file: */
#define S_IFDIR 0040000 /* directory */
#define S_IFCHR 0020000 /* character special */
#define S_IFBLK 0060000 /* block special */
#define S_IFREG 0100000 /* regular */
/* ... */
fsize
stat
fsize
#include <stdio.h>
#include <string.h>
#include "syscalls.h"
#include <fcntl.h> /* flags for read and write */
#include <sys/types.h> /* typedefs */
#include <sys/stat.h> /* structure returned by stat */
#include "dirent.h"
void fsize(char *);
/* print file sizes */
main(int argc, char **argv)
{
if (argc == 1) /* default: current directory */
fsize(".");
else
while (--argc > 0)
fsize(*++argv);
return 0;
}
fsize
fsize dirwalk
S_IFMT S_IFDIR <sys/stat.h>
&
==
182
int stat(char *, struct stat *);
void dirwalk(char *, void (*fcn)(char *));
/* fsize: print size of file "name" */
void fsize(char *name)
{
struct stat stbuf;
if (stat(name, &stbuf) == -1) {
fprintf(stderr, "fsize: can't access %s\n", name);
return;
}
if ((stbuf.st_mode & S_IFMT) == S_IFDIR)
dirwalk(name, fsize);
printf("%8ld %s\n", stbuf.st_size, name);
}
dirwalk
fsize
dirwalk
#define MAX_PATH 1024
/* dirwalk: apply fcn to all files in dir */
void dirwalk(char *dir, void (*fcn)(char *))
{
char name[MAX_PATH];
Dirent *dp;
DIR *dfd;
if ((dfd = opendir(dir)) == NULL) {
fprintf(stderr, "dirwalk: can't open %s\n", dir);
return;
}
while ((dp = readdir(dfd)) != NULL) {
if (strcmp(dp->name, ".") == 0
|| strcmp(dp->name, "..") == 0)
continue; /* skip self and parent */
if (strlen(dir)+strlen(dp->name)+2 > sizeof(name))
fprintf(stderr, "dirwalk: name %s/%s too
long\n",
dir, dp->name);
else {
sprintf(name, "%s/%s", dir, dp->name);
(*fcn)(name);
}
}
closedir(dfd);
}
183
readdir
"." ".."
opendir readdir
closedir
<sys/dir.h>
#ifndef DIRSIZ
#define DIRSIZ 14
#endif
struct direct /* directory entry */
{
ino_t d_ino; /* inode number */
char d_name[DIRSIZ]; /* long name does not have '\0' */
};
ino_t typedef
unsigned short
typedef
<sys/types.h>
opendir
fstat stat
int fstat(int fd, struct stat *);
/* opendir: open a directory for readdir calls */
DIR *opendir(char *dirname)
{
int fd;
struct stat stbuf;
DIR *dp;
if ((fd = open(dirname, O_RDONLY, 0)) == -1
|| fstat(fd, &stbuf) == -1
|| (stbuf.st_mode & S_IFMT) != S_IFDIR
|| (dp = (DIR *) malloc(sizeof(DIR))) == NULL)
return NULL;
dp->fd = fd;
return dp;
}
closedir
184
/* closedir: close directory opened by opendir */
void closedir(DIR *dp)
{
if (dp) {
close(dp->fd);
free(dp);
}
}
readdir read
static
#include <sys/dir.h> /* local directory structure */
/* readdir: read directory entries in sequence */
Dirent *readdir(DIR *dp)
{
struct direct dirbuf; /* local directory structure */
static Dirent d; /* return: portable structure */
while (read(dp->fd, (char *) &dirbuf, sizeof(dirbuf))
== sizeof(dirbuf)) {
if (dirbuf.d_ino == 0) /* slot not in use */
continue;
d.ino = dirbuf.d_ino;
strncpy(d.name, dirbuf.d_name, DIRSIZ);
d.name[DIRSIZ] = '\0'; /* ensure termination */
return &d;
}
return NULL;
}
fsize
Exercise 8-5 fsize
□
185
8.7 Example—A Storage Allocator
malloc free
malloc
typedef
malloc
malloc
malloc
double
int long
186
long
typedef long Align; /* for alignment to long boundary */
union header { /* block header: */
struct {
union header *ptr; /* next block if on free list */
unsigned size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
};
typedef union header Header;
Align
malloc
size
malloc
malloc
base freep NULL
malloc
freep
187
static Header base; /* empty list to get started */
static Header *freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void *malloc(unsigned nbytes)
{
Header *p, *prevp;
Header *morecore(unsigned);
unsigned nunits;
nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;
if ((prevp = freep) == NULL) { /* no free list yet */
base.s.ptr = freep = prevp = &base;
base.s.size = 0;
}
for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
if (p->s.size >= nunits) { /* big enough */
if (p->s.size == nunits) /* exactly */
prevp->s.ptr = p->s.ptr;
else { /* allocate tail end */
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freep = prevp;
return (void *)(p+1);
}
if (p == freep) /* wrapped around free list */
if ((p = morecore(nunits)) == NULL)
return NULL; /* none left */
}
}
morecore
malloc morecore NALLOC
morecore
free
sbrk(n) n
sbrk −1 NULL
−1 char *
sbrk
malloc
188
#define NALLOC 1024 /* minimum #units to request */
/* morecore: ask system for more memory */
static Header *morecore(unsigned nu)
{
char *cp, *sbrk(int);
Header *up;
if (nu < NALLOC)
nu = NALLOC;
cp = sbrk(nu * sizeof(Header));
if (cp == (char *) -1) /* no space at all */
return NULL;
up = (Header *) cp;
up->s.size = nu;
free((void *)(up+1));
return freep;
}
free freep
/* free: put block ap in free list */
void free(void *ap)
{
Header *bp, *p;
bp = (Header *)ap - 1; /* point to block header */
for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
break; /* freed block at start or end of arena */
if (bp + bp->s.size == p->s.ptr) { /* join to upper nbr */
bp->s.size += p->s.ptr->s.size;
bp->s.ptr = p->s.ptr->s.ptr;
} else
bp->s.ptr = p->s.ptr;
if (p + p->s.size == bp) { /* join to lower nbr */
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr;
} else
p->s.ptr = bp;
freep = p;
}
typedef union
189
sbrk
Exercise 8-6 calloc(n,size)
n size calloc
malloc □
Exercise 8-7 malloc
free
□
Exercise 8-8
bfree(p,n)
p
n malloc free bfree
□
